"""
source: http://www.matrix67.com/blog/archives/4790
        _____   _____
      _| +_7 |_| *_3 |_
2011->_  |_|  _  |_|  _ ->2012
       |_/_2_| |_-_5_|

"""

class Node:
    def __init__(self, label, calc, is_end=False):
        self.next = []
        self.label = label
        self.calc = calc
        self.end = is_end

    def get_next(self):
        return self.next

    def is_end(self):
        return self.end

    def add_next(self, node):
        self.next.append(node)

    def calc(self, value):
        return self.calc(value)

    def __str__(self):
        return self.label

def get_trace(nodes):
    return ' '.join([str(node) for node in nodes])

def _dfs(val, next_nodes, nodes, depth, depth_limit):
    if depth == depth_limit:
        print 'Failed: ' + get_trace(nodes)
        return

    for next_node in next_nodes:
        nodes.append(next_node)
        if next_node.is_end():
            if val == next_node.calc(0):
                print 'Ok: ' + get_trace(nodes)
                exit()
        else:
            _dfs(next_node.calc(val), next_node.get_next(), nodes, depth+1, depth_limit)
        nodes.pop()

def dfs(start_node, depth_limit=10):
    # wrapper
    _dfs(start_node.calc(0), start_node.get_next(), [start_node], 1, depth_limit)

if __name__ == '__main__':
    # create nodes
    begin_node = Node('2011', lambda x: 2011)
    plus7_node1 = Node('+7', lambda x: x+7)
    plus7_node2 = Node('+7', lambda x: x+7)
    divid2_node1 = Node('/2', lambda x: x/2)
    divid2_node2 = Node('/2', lambda x: x/2)
    mult3_node1 = Node('*3', lambda x: x*3)
    mult3_node2 = Node('*3', lambda x: x*3)
    subt5_node1 = Node('-5', lambda x: x-5)
    subt5_node2 = Node('-5', lambda x: x-5)
    end_node = Node('= 2012', lambda x: 2012, True)

    # configure state diagram
    begin_node.add_next(plus7_node1)
    begin_node.add_next(divid2_node2)
    plus7_node1.add_next(mult3_node1)
    plus7_node1.add_next(subt5_node2)
    plus7_node1.add_next(divid2_node1)
    divid2_node1.add_next(plus7_node1)
    plus7_node2.add_next(divid2_node2)
    divid2_node2.add_next(plus7_node2)
    divid2_node2.add_next(mult3_node1)
    divid2_node2.add_next(subt5_node2)
    mult3_node1.add_next(subt5_node1)
    mult3_node1.add_next(end_node)
    subt5_node1.add_next(divid2_node1)
    subt5_node1.add_next(plus7_node2)
    subt5_node1.add_next(mult3_node1)
    mult3_node2.add_next(divid2_node1)
    mult3_node2.add_next(plus7_node2)
    mult3_node2.add_next(subt5_node2)
    subt5_node2.add_next(mult3_node2)
    subt5_node2.add_next(end_node)

    dfs(begin_node, 30)
